package com.leetCode.ListNodeDemo;

import java.util.ArrayList;
import java.util.List;

public class SwapPairsDemo {

    public static void main(String[] args) {
        ListNode twoNode1 = new ListNode(1);
        ListNode twoNode2 = new ListNode(2);
        ListNode twoNode3 = new ListNode(3);
        ListNode twoNode4 = new ListNode(4);
        twoNode1.next = twoNode2;
        twoNode2.next = twoNode3;
        twoNode3.next = twoNode4;
        System.out.println(swapPairs(twoNode1));
    }

    /**
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
     * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     *
     * 示例 1：
     *
     *
     * 输入：head = [1,2,3,4]
     * 输出：[2,1,4,3]
     * 示例 2：
     *
     * 输入：head = []
     * 输出：[]
     * 示例 3：
     *
     * 输入：head = [1]
     * 输出：[1]
     * 提示：
     *
     * 链表中节点的数目在范围 [0, 100] 内
     * 0 <= Node.val <= 100
     * Related Topics
     * 递归
     * 链表
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        List<Integer> valList = new ArrayList<>();
        while (head != null){
            valList.add(head.val);
            head = head.next;
        }
        ListNode root = new ListNode();
        ListNode tailNode = null;
        int left = 0;
        while (left + 1 < valList.size()){
            Integer oneValue = valList.get(left + 1);
            Integer twoValue= valList.get(left);
            ListNode oneNode = new ListNode(oneValue);
            ListNode twoNode = new ListNode(twoValue);
            oneNode.next = twoNode;
            if (tailNode == null){
                root.next = oneNode;
            } else {
                tailNode.next = oneNode;
            }
            left = left + 2;
            tailNode = twoNode;
        }
        if (valList.size() % 2 > 0){
            if (tailNode == null){
                tailNode = root;
            }
            ListNode twoNode = new ListNode(valList.get(valList.size() - 1));
            tailNode.next = twoNode;
        }
        return root.next;
    }

    public static ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode tempNode = head;
        ListNode root = new ListNode();
        ListNode tailNode = null;
        while (tempNode != null){
            ListNode twoNode = new ListNode(tempNode.val);
            if (tempNode.next != null){
                ListNode oneNode = new ListNode(tempNode.next.val);
                if (tailNode == null){
                    root.next = oneNode;
                } else {
                    tailNode.next = oneNode;
                }
                oneNode.next = twoNode;
                tempNode = tempNode.next.next;
            } else {
                if (tailNode == null){
                    root.next = twoNode;
                } else {
                    tailNode.next = twoNode;
                }
                tempNode = tempNode.next;
            }
            tailNode = twoNode;
        }
        return root.next;
    }
}
